1. Field of the Invention
The present invention relates to a graphics transformation engine, and more particularly, to a process and apparatus for decomposing any arbitrary input polygons representing an image into trapezoids which can be rendered more efficiently by a raster scan conversion system.
2. Description of the Prior Art
Prior art raster graphics systems generally contain two distinct parts: a graphics transformation engine that transforms and lights the geometric description of a scene in accordance with the user's viewpoint and a renderer that paints the transformed scene onto a display screen. As is well known, the geometric description of the scene may comprise a combination of a plurality of polygons having an arbitrary number of sides. In other words, the 3-dimensional image to be displayed has been described as a surface composed of polygons of differing shadings. As used herein such a "polygon" refers to an ordered set of vertices V[1]. . . V[N] where N is the vertex count for the polygon. These vertices specify the N edges of the polygon, which are line segments E[1]. . . E[N] with end points made up of respective vertices V[1]. . . V[N]. For example, line segment E[1] may have end points V[1] and V[2], while line segment E[2] has end points V[2] and V[3]. Such polygons may be identified by the graphics transformation engine as a sequence of graphics primitives including information such as the coordinates (X,Y,Z) of the vertices of each polygon as well as the shading information for each of the vertices and instructions which are processed in the graphics transformation engine for all pixel-level rendering computations.
Such geometric representations of a scene greatly facilitate the processing by a graphics transformation engine which is necessary for rendering the pixel image data to the display screen. The graphics transformation engines typically perform many tasks on such data including graphics context management, matrix transformation calculations, spline tessellation and lighting model computations. The transformation engines may also control vector and polygon rendering hardware. However, such computations are generally quite complex and timeconsuming and require much processing power, and the resulting processing difficulties have often been the primary limitation upon the speed by which images may be rendered in conventional raster graphics systems.
The most common proposal for solving the abovementioned problem has been to increase the processing power of the graphics transformation engines. For example, a plurality of transformation engines have been provided in parallel so that the processing of each of the respective polygons may be performed in parallel. However, such systems are quite complicated and expensive and still do not process the polygons efficiently. As a result, the processing efficiency for graphics primitives information has bee heretofore severely limited. Thus, it is desirable that means be provided for improving the processing efficiency of graphics transformation engines so that even complex 3-dimensional images containing numerous simple polygons may be rendered at interactive rates.
It has been previously proposed to render polygons representing an image onto a display screen in a vector display system by breaking the input polygons into trapezoids. For example, Lee proposes in "Shading of Regions on Vector Display Devices," Computer Graphics, Vol. 15, No. 3, August 1981, a technique for breaking an arbitrary simple polygon of a graphics vector display system into a plurality of trapezoids for rendering on the display screen. In particular, Lee proposes an algorithm for shading the interior of an arbitrary simple polygon having N vertices with a set of parallel lines where the slope and the distance between the lines are pre-specified. The algorithm of Lee for rendering an arbitrary simple polygon P represents the polygon as an ordered list of vertices forming respective straight-line segments, or edges, between vertices where no two non-consecutive edges intersect (i.e., crossing edges cannot be rendered). Lee breaks the input polygons into a plurality of trapezoids for shading since in a vector scanning system of the type proposed by Lee, all the shading lines are typically horizontal (i.e., the shading is accomplished by rendering a plurality of horizontal vectors between the polygon's edges).
In Lee's rendering system, the vertices of the polygon are described in accordance with their relationship with the y-axis. In particular, the vertices are defined as to whether they are a local minimum (stalactitic) in the y-direction, a local maximum (stalagmitic) in the y-direction, or are regular vertices. Le sorts the vertices of the polygon according to their y-coordinates and then examines each of the vertices to determine whether they are local minima, local maxima, or regular vertices. The vertices are then linearly scanned from bottom to top, and a list of segments of critical lines (horizontal lines passing through a vertex) that are interior to the polygon and a linked list of edges is also maintained. The edges in the linked list are ordered from left to right according to the intersection points of these edges with the critical lines. Then, when each vertex is scanned, different operations are performed depending upon the type of vertex encountered. The algorithm terminates when the topmost vertex is scanned or the linked list is empty.
As previously noted, the system of Lee is described only with respect to a vector display system and operates only for simple polygons having no two non-consecutive edges which intersect (i.e., edges may cross only at the vertices). Moreover, the algorithm of Lee relies upon the classification of each of the vertices of the input polygon and thus requires substantial setup before the algorithm can be performed. As a result, a complex polygon with intersecting edges cannot be rendered by Lee's system. Moreover, there is no indication in the prior art as to how the technique taught by Lee could be used to render points in a pixel display system. Since it is desirable for a rendering system to be able to render any input polygon, no matter how complicated, at a sufficient execution speed so that even complex three-dimensional images containing numerous complex polygons may be rendered at interactive rates, substantial improvement upon the rendering system of Lee remains necessary.
Accordingly, there is a long-felt need in the art for a polygon rendering system in which complex polygons, even those having crossing edges, can be processed and rendered at truly interactive rates. The present invention has been designed to meet these needs.